package huawei.bfs;

/**
 * https://leetcode-cn.com/problems/coin-change/
 */
public class J322 {
    public static void main(String[] args){
        System.out.println(coinChange(new int[]{1,2,5},11));
        System.out.println(coinChange(new int[]{2},3));
        System.out.println(coinChange(new int[]{1},0));
        System.out.println(coinChange(new int[]{474,83,404,3
        },264));
    }
    public static int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        for (int i = 1; i <= amount; i++) {
            int min = Integer.MAX_VALUE;
            for (int coin : coins) {
                if (i - coin < 0) {
                    continue;
                }
                min = Math.min(min, dp[i - coin]);
            }
            dp[i] = min ==Integer.MAX_VALUE?min:min+ 1;
        }
        return dp[amount]==Integer.MAX_VALUE?-1:dp[amount];
    }
}
